package StuDemo.LinkedList;

/**
 * @Author：DijaH
 * @Date：2023/4/5 6:59 下午
 * @Version：1.0.0
 * @Description： 判断一个连表是否有环
 * 只需要使用快慢指针，如果两个有相等的时候就说明有环
 */
public class code5_hasCycle {

    /**
     * 判断这个链表中是否有环
     * @param head
     * @return
     */
    public static boolean hasCycle(ListNode head){
        ListNode fast,slow;
        fast = slow = head;
        while (fast.next != null && fast != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

    /**
     * 返回这个链表环的起始的位置
     *
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head){
        ListNode fast,slow;
        fast = slow = head;
        while (fast.next != null && fast != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        //回到起始的位置，将一个指针重新定向的head的位置
        slow = head;
        while (slow != fast){
            //这个时候就以相等的速度前进，直到相等
            fast = fast.next;
            slow = slow.next;
        }
        //最终返回slow的位置，就是环的起始的位置
        return slow;
    }


}
